from collections import deque


class BreadthFirstSearch:
    def __init__(self, graph):
        self.graph = graph

    def breadth_first_search(self, start):
        """
        Perform breadth-first search on the graph starting from the given start node.

        Args:
            start: The start node for the breadth-first search.

        Returns:
            List: Nodes visited during the breadth-first search in the order they were visited.
        """
        if start not in self.graph:
            return []

        queue = deque([start])
        visited = set()
        result = []

        while queue:
            node = queue.popleft()
            visited.add(node)
            result.append(node)

            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

        return result

    def bidirectional_breadth_first_search(self, start, target):
        """
        Perform bidirectional breadth-first search on the graph to find the shortest path between start and target nodes.

        Args:
            start: The start node for the bidirectional breadth-first search.
            target: The target node for the bidirectional breadth-first search.

        Returns:
            List: Nodes visited during the bidirectional breadth-first search in the order they were visited.
                  If a path is found, the list represents the shortest path from the start to the target node.
                  If no path is found, an empty list is returned.
        """
        if start not in self.graph or target not in self.graph:
            return []

        if start == target:
            return [start]

        forward_queue = deque([start])
        backward_queue = deque([target])
        forward_visited = {start}
        backward_visited = {target}
        forward_parent = {start: None}
        backward_parent = {target: None}
        common_node = None

        while forward_queue and backward_queue:
            forward_node = forward_queue.popleft()
            backward_node = backward_queue.popleft()

            if forward_node in backward_visited:
                common_node = forward_node
                break

            if backward_node in forward_visited:
                common_node = backward_node
                break

            for neighbor in self.graph[forward_node]:
                if neighbor not in forward_visited:
                    forward_queue.append(neighbor)
                    forward_visited.add(neighbor)
                    forward_parent[neighbor] = forward_node

            for neighbor in self.graph[backward_node]:
                if neighbor not in backward_visited:
                    backward_queue.append(neighbor)
                    backward_visited.add(neighbor)
                    backward_parent[neighbor] = backward_node

        if common_node is None:
            return []

        path = [common_node]
        current_node = common_node

        while current_node != start:
            current_node = forward_parent[current_node]
            path.insert(0, current_node)

        current_node = common_node

        while current_node != target:
            current_node = backward_parent[current_node]
            path.append(current_node)

        return path

    def zero_one_breadth_first_search(self, start):
        """
        Perform 0-1 breadth-first search on the graph starting from the given start node.

        Args:
            start: The start node for the 0-1 breadth-first search.

        Returns:
            List: Nodes visited during the 0-1 breadth-first search in the order they were visited.
        """
        if start not in self.graph:
            return []

        queue = deque([(start, 0)])
        visited = {start}
        result = []

        while queue:
            node, level = queue.popleft()
            result.append((node, level))

            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    if level == 0:
                        queue.append((neighbor, 1))
                    else:
                        queue.append((neighbor, 0))

                    visited.add(neighbor)

        return result

if __name__ == "__main__":
    # Create a graph
    graph = {
        'A': ['B', 'E'],
        'B': ['A', 'C', 'D'],
        'C': ['B', 'F'],
        'D': ['B', 'E'],
        'E': ['A', 'D'],
        'F': ['G', 'H', 'C'],
        'G': ['F'],
        'H': ['F']
    }

    bfs = BreadthFirstSearch(graph)

    # Perform breadth-first search
    start_node = 'A'
    bfs_result = bfs.breadth_first_search(start_node)
    print("Breadth-First Search:")
    print(bfs_result)
    # Output:
    # Breadth-First Search:
    # ['A', 'B', 'E', 'C', 'D']

    # Perform bidirectional breadth-first search
    start_node = 'A'
    target_node = 'H'
    bidirectional_bfs_result = bfs.bidirectional_breadth_first_search(start_node, target_node)
    print("Bidirectional Breadth-First Search:")
    print(bidirectional_bfs_result)
    # Output:
    # Bidirectional Breadth-First Search:
    # ['A', 'B', 'C']

    # Perform 0-1 breadth-first search
    start_node = 'A'
    zero_one_bfs_result = bfs.zero_one_breadth_first_search(start_node)
    print("0-1 Breadth-First Search:")
    print(zero_one_bfs_result)
    # Output:
    # 0-1 Breadth-First Search:
    # [('A', 0), ('B', 1), ('E', 0), ('C', 1), ('D', 0)]
